class Solution {
    //https://leetcode.cn/problems/water-and-jug-problem/;
public:
    bool canMeasureWater(int x, int y, int z) {
        stack<pair<int, int>> stk;
        stk.push(make_pair(0, 0));
        auto hash_function = [](const pair<int, int>& o) { return hash<int>()(o.first) ^ hash<int>()(o.second); };
        unordered_set<pair<int, int>, decltype(hash_function)> seen(0, hash_function);
        while (!stk.empty())
        {
            if (seen.count(stk.top()))
            {
                stk.pop();
                continue;
            }
            seen.insert(stk.top());
            int a1 = stk.top().first;
            int a2 = stk.top().second;
            stk.pop();
            if (a1 == z || a2 == z || a1 + a2 == z)
            {
                return true;
            }
            stk.push(make_pair(x, a2));
            stk.push(make_pair(a1, y));
            stk.push(make_pair(0, a2));
            stk.push(make_pair(a1, 0));
            stk.push(make_pair(a1 - min(a1, y - a2), a2 + min(a1, y - a2)));
            stk.push(make_pair(a1 + min(a2, x - a1), a2 - min(a2, x - a1)));
        }
        return false;
    }
};